返回首页 C++ 模板

树形算法之最近公共祖先 (LCA) 朴素求法

一步一步往上爬的直觉解法（暴力法）

最近公共祖先 LCA 朴素算法 暴力求解 树 CSP-J 
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 500005;
int depth[MAXN];     // 记录每个节点的深度（楼层）
int pa[MAXN];     // 记录每个节点的直接父节点 (不需要倍增数组了)
vector<int> tree[MAXN]; 

// DFS 预处理：只计算深度和直接父节点
void dfs(int u, int fa) {
    depth[u] = depth[fa] + 1; // 楼层 = 父亲楼层 + 1
    pa[u] = fa;               // 记录直接老爸是谁

    // 遍历所有子节点
    for (int v : tree[u]) {
        if (v != fa) {
            dfs(v, u);
        }
    }
}

// 求解 x 和 y 的 LCA (朴素法：一步步爬楼梯)
int lca_naive(int x, int y) {
    // 1. 深度对齐：让比较深的节点（楼层低的）先往上爬
    // 确保 x 始终是更深的那个
    if (depth[x] < depth[y]) {
        swap(x, y); 
    }

    // x 一步一步往上爬，直到和 y 在同一层
    while (depth[x] > depth[y]) {
        x = pa[x];
    }

    // 如果对齐高度后，俩人已经在同一个位置了，那这就是 LCA
    if (x == y) return x;

    // 2. 手拉手一起走：两人一起一步一步往上爬，直到相遇
    while (x != y) {
        x = pa[x];
        y = pa[y];
    }

    // 相遇的地方就是最近公共祖先
    return x; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, root;
    cin >> n >> m >> root;

    // 建树
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // 预处理
    dfs(root, 0);

    // 处理查询
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        cout << lca_naive(a, b) << '\n';
    }

    return 0;
}

📖 要点说明

⚠️ 常见错误